Reclaiming unused storage space in de-duplicated file systems is challenging because files share data segments or data chunks. Once a file is deleted, storage space assigned to its data segments or data chunks may not be reclaimed unless they are not shared by other files. Mark-and-sweep garbage collection approach has been used to solve this problem. This approach typically includes the steps of traversing the entire file system, marking all data segments used in the file system as alive, and reclaiming storage space taken up by all unused data segments. However, such an approach is currently not scalable in de-duplicated multi-controller file systems since it is largely a synchronous process and conflicts often arise and must be resolved when multiple controllers are attempting to access the same data segment or data block. As such, an improved method for reclaiming unused storage space in a de-duplicated multi-controller file system is needed.